Concerning the problem about the identification and evolution of enterprise trust alliance in dynamic trust network, a Graph Clustering (GC) algorithm based on fragment was proposed. Firstly, by considering the time information of network evolution, the trust network of enterprise was encoded. Secondly, the evaluation function of coding cost for dividing and presenting the structure of trust network was built. When the trust alliance was stable, the trust network during this time period would be compressed into a fragment; when the alliance changed, a new trust network fragment would be built and the structure of it would be re-devided. Finally, by finding the minimum coding cost, the stable structure of trust alliance and the timestamp of structural mutation could be found. The experimental results indicate that the proposed algorithm can identify the enterprise trust alliances and their mutations; and the accuracy and operating efficiency are higher than the classical community discovery algorithm.